package com.cat.graphTheory;

import java.util.List;
import java.util.PriorityQueue;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/smallest-range-covering-elements-from-k-lists/description/
 * @create 2025/10/7 21:36
 * @since JDK17
 */

public class Solution42 {
    public int[] smallestRange(List<List<Integer>> nums) {
        int n = nums.size(), max = Integer.MIN_VALUE;
        int[] ans = new int[]{0, Integer.MAX_VALUE}, idx = new int[n];
        PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        for (int i = 0; i < n; i++) {
            int num = nums.get(i).get(0);
            idx[i] = 1;
            max = Math.max(max, nums.get(i).get(0));
            heap.add(new int[]{num, i});    //
        }
        while (true) {  //
            var x = heap.poll();
            if (max - x[0] < ans[1] - ans[0]) { //
                ans[0] = x[0];
                ans[1] = max;
            }
            if (idx[x[1]] == nums.get(x[1]).size()) {   // 已经有一个走到头了
                break;
            }
            int next = nums.get(x[1]).get(idx[x[1]]++);
            max = Math.max(max, next);
            heap.add(new int[]{next, x[1]});
        }

        return ans;
    }
}
